BZOJ 2756 奇怪的游戏

Description

Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩,每个格子有一个数。每次 Blinker 会选择两个相邻
的格子,并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同
一个数则输出-1。

Input

输入的第一行是一个整数T,表示输入数据有T轮游戏组成。
每轮游戏的第一行有两个整数N和M, 分别代表棋盘的行数和列数。
接下来有N行,每行 M个数。

Output

对于每个游戏输出最少能使游戏结束的次数,如果永远不能变成同一个数则输出-1。

Sample Input

2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2

Sample Output

2
-1

Hint

【数据范围】
对于30%的数据,保证 T<=10,1<=N,M<=8
对于100%的数据,保证 T<=10,1<=N,M<=40,所有数为正整数且小于1000000000

Solution

这题要好J形有好J形
黑白染个色
首先如果nm是偶数,黑白和一定要相等
之后可以二分+网络流判定出最后的值,然后在算出要加多少次
如果n
m是奇数,黑色格子和-白色格子和就是最后的值(假设黑色多)
同样网络流判定一下,然后如果可以就输出这个值
(谁能告诉我为什么奇偶不同最后输出的东西不同[微笑])

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<bits/stdc++.h>

#define maxd 40+5
#define maxn 1600+5
#define maxm 16000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct sides{
int u,v;ll c;
int next;
}s[maxm];

queue<int> q;
ll lim,sum,ans,upper=(ll)1<<60;
int a[maxd][maxd],h[maxn];
int first[maxn],cur[maxn],ind;
int n,m,S,T,Q;
int st[2][4]={{1,0,-1,0},{0,1,0,-1}};

void insert(int u,int v,ll c)
{

s[ind]=(sides){u,v,c,first[u]},first[u]=ind++;
s[ind]=(sides){v,u,0,first[v]},first[v]=ind++;
}

int hash(int x,int y)
{

return (x-1)*m+y;
}

bool bfs()
{

set(h,-1),h[T]=0;
q.push(T);
while( !q.empty() ){
int sd=q.front();q.pop();
for(int i=first[sd];i!=-1;i=s[i].next)
if( s[i^1].c>0 && h[s[i].v]==-1 ){
h[s[i].v]=h[sd]+1;
q.push(s[i].v);
}
}
return h[S]!=-1;
}

ll dfs(int x,ll flow)
{

if( x==T ) return flow;
ll used=0;
for(int &i=cur[x];i!=-1;i=s[i].next)
if( s[i].c>0 && h[s[i].v]+1==h[x] ){
ll w=dfs(s[i].v,min(s[i].c,flow-used));
s[i].c-=w,s[i^1].c+=w;
used+=w;
if( used==flow ) return flow;
}
return used;
}

void dinic()
{

ans=0;
while( bfs() ){
memcpy(cur,first,sizeof(cur));
ans+=dfs(S,LLONG_MAX);
}
if( ans!=lim ) ans=-1;
}

bool get(ll x)
{

set(first,-1),ind=lim=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if( a[i][j]<=x ){
if( (i+j)%2 ){
for(int k=0;k<4;k++){
int sx=i+st[0][k],sy=j+st[1][k];
if( sx>=1 && sx<=n && sy>=1 && sy<=m )
insert(hash(i,j),hash(sx,sy),LLONG_MAX);
}
insert(S,hash(i,j),x-a[i][j]);
}
else insert(hash(i,j),T,x-a[i][j]),lim+=x-a[i][j];
}
else return false;
return true;
}

void binary()
{

ll l=0,r=upper;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
l=max(l,(ll)a[i][j]);
while( l!=r ){
ll mid=(l+r)/2;
get(mid),dinic();
if( ans!=-1 ) r=mid;
else l=mid+1;
}
ans=l;
}

void getans(int x)
{

ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if( (i+j)%2 ) ans+=x-a[i][j];
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("2756.in","r",stdin);
freopen("2756.out","w",stdout);
#endif
scanf("%d",&Q);
while( Q-- ){
scanf("%d%d",&n,&m);
S=0,T=n*m+1,sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
if( (i+j)%2 ) sum-=a[i][j];
else sum+=a[i][j];
}
if( (n*m%2)==0 ){
if( sum!=0 ){
puts("-1");
continue;
}
else{
binary(),getans(ans);
printf("%lld\n",ans);
}
}
else{
bool flag=get(sum);
if( flag ){
dinic();
printf("%lld\n",ans);
}
else puts("-1");
}
}
return 0;
}